package leetcode.code1985;



import leetcode.IDebug;
import leetcode.helper.H;
// 快排改
public class Solution implements IDebug {

	public String kthLargestNumber(String[] nums, int k) {
		return kthLargestNumber(nums, 0, nums.length - 1, k);
	}

	private String kthLargestNumber(String[] nums, int L, int R, int k) {
		int randomIndex = (int) (Math.random() * (R - L + 1)) + L;
		int index = this.sort(nums, L, R, randomIndex);
		if (index == k - 1) {
			return nums[index];
		} else if (index < k - 1) {
			return this.kthLargestNumber(nums, index + 1, R, k);
		} else {
			return this.kthLargestNumber(nums, L, index - 1, k);
		}
	}

	private int sort(String[] nums, int L, int R, int index) {
		this.swap(nums, index, R);
		String num = nums[R];
		int p = L;
		for (int i = L; i < R; i++) {
			if (nums[i].length() > num.length() || (nums[i].length() == num.length() && nums[i].compareTo(num) >= 0)) {
				this.swap(nums, p++, i);
			}
		}
		this.swap(nums, p, R);
		return p;
	}

	private void swap(String[] nums, int index, int r) {
		String tmp = nums[index];
		nums[index] = nums[r];
		nums[r] = tmp;
	}

	@Override
	public void debug4() {
		H.compare("1", this.kthLargestNumber(H.str2array2("[\"2\",\"21\",\"12\",\"1\"]"), 4));
		H.compare("2", this.kthLargestNumber(H.str2array2("[\"12\",\"12\",\"2\",\"2\"]"), 3));
		H.compare("3", this.kthLargestNumber(H.str2array2("[\"3\",\"6\",\"7\",\"10\"]"), 4));
		H.compare("0", this.kthLargestNumber(H.str2array2("[\"0\",\"0\"]"), 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
